\documentclass[a4paper,12pt,twocolumn]{article}
\usepackage{graphicx}
\usepackage{listings}
\usepackage[justification=centering]{caption}
\usepackage{subfigure}  
\usepackage{multirow}
\usepackage{balance}
\usepackage{gensymb}
\lstset{language=Matlab}
\lstset{breaklines}
\lstset{extendedchars=false}

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\theoremstyle{definition}
\newtheorem{thm}{Theorem}
\newtheorem{exmp}{Example}
\newtheorem{defn}{Definition}
\newtheorem{lema}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{coro}{Corollary}

\newcommand{\GreekAlpha}[1]{\uppercase\expandafter{\romannumeral#1}}
\newcommand{\Greekalpha}[1]{\lowercase\expandafter{\romannumeral#1}}
\renewcommand{\baselinestretch}{1.25}

%------------setlength----------------%
\setlength{\textwidth}{162mm}
%\setlength{\textheight}{190mm}
\setlength{\textheight}{231mm}
\setlength{\headheight}{-0.1cm}
\setlength{\topmargin}{-0.1cm}
\setlength{\oddsidemargin}{-0cm}
\setlength{\evensidemargin}{-0cm}

\setlength\columnsep{12pt}
\setlength\columnseprule{0.4pt}

\setlength{\parskip}{1mm}
\setlength{\unitlength}{1mm}
\setlength{\parindent}{2em}

\title{Numerical Analysis Homework \#5}

\author{Li Zhiqi\quad 3180103041 , }

\begin{document}
\maketitle
\section{Theoretical questions}
\GreekAlpha{1}.\\
We need to prove $\mathcal{C}[a,b]$ is an inner product space over
$\mathbb{R}$ with
respect to
\begin{align*}
  \left \langle u,v \right \rangle = \int_{a}^{b} \rho(t)u(t)\overline{v(t)}\text{d}t.
\end{align*}
Firstly, it's easy to check that $\mathcal{C}[a,b]$ satisfies
(VSA-1)-(VSA-7) in Definition B.2, hence it's a vector space. Next we
check the condition in Definition B.108.
\begin{align*}
  \text{(IP-1)}&\forall f \in \mathcal{C}[a,b], \\
  \left \langle f,f \right
  \rangle &= \int_{a}^{b} \rho(t)|f(t)|^2\text{d}t \ge 0.
\end{align*}
The last inequality follows from $\rho(t) > 0$.
\begin{align*}
  \text{(IP-2)} \left \langle f,f \right
  \rangle = 0 \Leftrightarrow f(t)\equiv 0 , \forall t \in [a,b].
\end{align*}
The sufficiency is obvious. For the necessity, it's easy to prove by
contradiction.
\begin{align*}
  \text{(IP-3)} &\forall f,g,h \in \mathcal{C}[a,b], \\
  \left \langle f+g,h \right
    \rangle &= \int_{a}^{b} \rho(t)(f(t)+g(t))\overline{h(t)}\text{d}t\\
                &= \int_{a}^{b} \rho(t)f(t)\overline{h(t)}\text{d}t \\
  &\ + \int_{a}^{b}
    \rho(t)g(t)\overline{h(t)}\text{d}t\\
  &= \left \langle f,h \right \rangle + \left \langle g,h \right \rangle.
\end{align*}
\begin{align*}
  \text{(IP-4)} &\forall f,g\in \mathcal{C}[a,b], \forall s \in \mathbb{R}, \\
   \left \langle sf,g \right
    \rangle &= \int_{a}^{b} \rho(t)sf(t)\overline{g(t)}\text{d}t\\
                &= s\int_{a}^{b} \rho(t)f(t)\overline{g(t)}\text{d}t \\
  &= s\left \langle f,g \right \rangle.
\end{align*}
\begin{align*}
  \text{(IP-5)} &\forall f,g\in \mathcal{C}[a,b], \\
   \left \langle f,g \right
    \rangle &= \int_{a}^{b} \rho(t)f(t)\overline{g(t)}\text{d}t\\
                &= \overline{\int_{a}^{b} \rho(t)g(t)\overline{f(t)}\text{d}t} \\
  &= \overline{\left \langle g,f \right \rangle},
\end{align*}
where the second step follows from $\rho(t) \in \mathbb{R}$.\\
With (IP-1)-(IP-5), we show that $\mathcal{C}[a,b]$ is indeed an inner
product space. Then naturally $\mathcal{C}[a,b]$ becomes a normed
vector space over $\mathbb{R}$ with respect to
\begin{align*}
  \|u\|_2 = \sqrt{\left \langle u,u  \right \rangle} = (\int_{a}^{b} \rho(t)|u(t)|^2\text{d}t)^{\frac{1}{2}}.
\end{align*}
\GreekAlpha{2}.\\
(a) With $T_n = \cos{(n\arccos{x})}$, we have
\begin{align*}
  & \forall m \ne n, \left \langle T_n,T_m  \right \rangle \\
  &= \int_{-1}^{1} \frac{1}{\sqrt{1-x^2}}T_n(x)T_m(x)\text{d}x\\
  &= \int_{-1}^{1}
    \frac{1}{\sqrt{1-x^2}}\cos{(n\arccos{x})}\\
  &\quad \quad \quad \cos{(m\arccos{x})}\text{d}x\\
  &= \int_{0}^{\pi}
    \cos{nt}\cos{mt}\text{d}t\\
  &=\frac{1}{2}\int_{-\pi}^{\pi}
    \cos{nt}\cos{mt}\text{d}t = 0.
\end{align*}
Here the third step is from setting $t = \arccos{x}$, and the last
step from the fact that $\cos{nx}$ and $\cos{mx}$ are orthogonal in
$L_{\rho = 1}^2[-\pi,\pi]$.\\
Similarily,
\begin{align*}
  & \forall n > 0, \left \langle T_n,T_n  \right \rangle \\
  &= \int_{-1}^{1} \frac{1}{\sqrt{1-x^2}}T_n(x)^2\text{d}x\\
  &= \int_{-1}^{1}
    \frac{1}{\sqrt{1-x^2}}\cos^2{(n\arccos{x})}\text{d}x\\
  &= \int_{0}^{\pi}
    \cos^2{(nt)}\text{d}t\\
  &=\frac{\pi}{2}\int_{-\pi}^{\pi}
    (\frac{\cos{nt}}{\sqrt{\pi}})^2\text{d}t = \frac{\pi}{2}.\\
  &\left \langle T_0,T_0  \right \rangle =\int_{-1}^{1} \frac{1}{\sqrt{1-x^2}}\text{d}x = \pi.
\end{align*}
(b) By definition $T_n = \cos{(n\arccos{x})}$, we have
\begin{align*}
  T_0(x) &= 1,\\
  T_1(x) &= x,\\
  T_2(x) &= 2x^2-1,\\
  T_3(x) &= 4x^3-3x.
\end{align*}
By (a), $\forall n > 0$, $\|T_n\|^2 = \frac{\pi}{2}$, and $\|T_0\|^2 = \pi$, hence
\begin{align*}
  u_0^* &= \sqrt{\frac{1}{\pi}},\\
  u_1^* &= \sqrt{\frac{2}{\pi}}x,\\
  u_2^* &= \sqrt{\frac{2}{\pi}}(2x^2-1),\\
  u_3^* &= \sqrt{\frac{2}{\pi}}(4x^3-3x).
\end{align*}
\GreekAlpha{3}.\\
(a) With $u_0^*,u_1^*,u_2^*$ in \GreekAlpha{2}, we compute that
\begin{align*}
  \left \langle y,u_0^*  \right \rangle &= \int_{-1}^{1}
  \sqrt{\frac{1}{\pi}}\text{d}x = 2\sqrt{\frac{1}{\pi}},\\
  \left \langle y,u_1^*  \right \rangle &= \int_{-1}^{1}
                                          \sqrt{\frac{2}{\pi}}x\text{d}x = 0,\\
  \left \langle y,u_2^*  \right \rangle &= \int_{-1}^{1}
  \sqrt{\frac{2}{\pi}}(2x^2-1)\text{d}x = -\frac{2}{3}\sqrt{\frac{2}{\pi}}.
\end{align*}
Hence
\begin{align*}
  \varphi_2 &=  \left \langle y,u_0^*  \right \rangle u_0^* + \left
  \langle y,u_1^*  \right \rangle u_1^* + \left \langle y,u_2^*
  \right \rangle u_2^*\\
  &= -\frac{2}{3}\sqrt{\frac{2}{\pi}}[\sqrt{\frac{2}{\pi}}(2x^2-1)] +
    2\sqrt{\frac{1}{\pi}}\sqrt{\frac{1}{\pi}}\\
  &= -\frac{8}{3\pi}x^2 + \frac{10}{3\pi}.
\end{align*}
(b) To get normal equation, we compute
\begin{align*}
  \left \langle 1,1  \right \rangle &= \|T_0\|^2 = \pi,\\
  \left \langle 1,x  \right \rangle &= \int_{-1}^{1}
                                      \frac{x}{\sqrt{1-x^2}}\text{d}x = 0,\\
  \left \langle x,x  \right \rangle &= \left \langle 1,x^2  \right
                                      \rangle = \|T_1\|^2 =
                                      \frac{\pi}{2},\\
  \left \langle x,x^2  \right \rangle &= \int_{-1}^{1}
                                      \frac{x^3}{\sqrt{1-x^2}}\text{d}x
                                        = 0,\\
  \left \langle x^2,x^2  \right \rangle &= \int_{-1}^{1}
                                      \frac{x^4}{\sqrt{1-x^2}}\text{d}x = \frac{3}{8}\pi,\\
\end{align*}
where the last equation comes from the fact that
\begin{align*}
  \|T_2\|^2 = \int_{-1}^{1}\frac{4x^4 - 4x^2 +
  1}{\sqrt{1-x^2}}\text{d}x = \frac{\pi}{2}.
\end{align*}
and
\begin{align*}
  &\int_{-1}^{1}\frac{x^2}{\sqrt{1-x^2}}\text{d}x = \frac{\pi}{2},\\
  &\int_{-1}^{1}\frac{1}{\sqrt{1-x^2}}\text{d}x = \pi.
\end{align*}
Combining
\begin{align*}
  \left \langle 1,y  \right \rangle &= \int_{-1}^{1}
                                      1\text{d}x = 2,\\
  \left \langle x,y  \right \rangle &= \int_{-1}^{1}
                                      x\text{d}x = 0,\\
  \left \langle x^2,y  \right \rangle &= \int_{-1}^{1}
                                      x^2\text{d}x = \frac{2}{3},
\end{align*}
we get the normal equation
\begin{align*}
  \begin{bmatrix}
  \pi& 0 & \frac{\pi}{2}\\
  0& \frac{\pi}{2} &0 \\
  \frac{\pi}{2}&0 & \frac{3}{8}\pi&
\end{bmatrix}
\begin{bmatrix}
 b_0\\
 b_1\\
 b_2
\end{bmatrix}
  =
  \begin{bmatrix}
 2\\
 0\\
 \frac{2}{3}
\end{bmatrix},
\end{align*}
which implies $b_0 = \frac{10}{3\pi}, b_1 = 0, b_2 = -\frac{8}{3\pi}$.
Hence
\begin{align*}
  \varphi_2 = -\frac{8}{3\pi}x^2 + \frac{10}{3\pi}.
\end{align*}
\GreekAlpha{4}.\\
(a) We use $\sum$ to represent $\sum_{i=1}^{N}$ in this problem.\\
$v_0 = u_0 = 1$, $\|v_0\|^2 = \sum 1 = 12$, $u_0^* =
\sqrt{\frac{1}{12}}$.\\
$u_1 = x$,
\begin{align*}
  v_1 &= u_1 - \left \langle u_1,u_0^*  \right \rangle u_0^*\\
  &= x - \left \langle x,\sqrt{\frac{1}{12}} \right \rangle
    \sqrt{\frac{1}{12}}\\
  &= x - \frac{1}{12}\sum x = x - \frac{13}{2}.
\end{align*}
\begin{align*}
  \|v_1\|^2 &= \sum (x - \frac{13}{2})^2 = 143,\\
  u_1^* &= \sqrt{\frac{1}{143}}(x - \frac{13}{2}).
\end{align*}
$u_2 = x^2$,
\begin{align*}
  v_2 &= u_2 - \left \langle u_2,u_1^*  \right \rangle u_1^* - \left \langle u_2,u_0^*  \right \rangle u_0^*\\
  &= x^2 - \left \langle x^2,\sqrt{\frac{1}{143}}(x - \frac{13}{2})
    \right \rangle \sqrt{\frac{1}{143}}(x - \frac{13}{2})
  \\
  &- \left \langle x^2,\sqrt{\frac{1}{12}} \right \rangle
    \sqrt{\frac{1}{12}}\\
      &= x - \frac{1}{143}(\sum x^2(x - \frac{13}{2}))(x - \frac{13}{2}) - \frac{1}{12}\sum
    x^2 \\
  &= x^2 - 13x + \frac{91}{3}.
\end{align*}
\begin{align*}
\|v_2\|^2 &= \sum (x^2 - 13x + \frac{91}{3})^2 =
  \frac{4004}{3},\\
  u_2^* &= \sqrt{\frac{3}{4003}}(x^2 - 13x + \frac{91}{3}). \\  
\end{align*}
Hence
\begin{align*}
  u_0^* &=
  \sqrt{\frac{1}{12}},u_1^* = \sqrt{\frac{1}{143}}(x - \frac{13}{2}),\\
  u_2^* &= \sqrt{\frac{3}{4004}}(x^2 - 13x + \frac{91}{3}).
\end{align*}
(b) 
With $u_0^*,u_1^*,u_2^*$ in \GreekAlpha{2}, we compute that
\begin{align*}
  b_0 = \left \langle y,u_0^*  \right \rangle &=
                                                \sqrt{\frac{1}{12}}\sum
                                                y = \frac{1662}{\sqrt{12}}
                                          ,\\
  b_1 = \left \langle y,u_1^*  \right \rangle &= \sqrt{\frac{1}{\sqrt{143}}}\sum y(x - \frac{13}{2})=\frac{589}{\sqrt{143}},\\
  b_2 = \left \langle y,u_2^*  \right \rangle &=
                                                \sqrt{\frac{3}{4004}}\sum
                                                y(x^2 - 13x +
                                                \frac{91}{3})\\
  &=12068\sqrt{\frac{3}{4004}}.
\end{align*}
Hence
\begin{align*}
  \hat{\varphi} &=  b_0 u_0^* + b_1 u_1^* + b_2 u_2^*\\
  &=
    \frac{1662}{\sqrt{12}}\sqrt{\frac{1}{12}}+\frac{589}{\sqrt{143}}\sqrt{\frac{1}{143}}(x
    -
    \frac{13}{2})\\
  &+12068\sqrt{\frac{3}{4004}}\sqrt{\frac{3}{4004}}(x^2
    - 13x + \frac{91}{3})\\
  &=9.042x^2 - 113.427x + 386.000,
\end{align*}
which is the same as the result in Example 5.49.\\
(c) The method using normal equation can be reused, for the matrix
$G(1,x,x^2)$ stay the same when $y_i$'s are different. The method
using orthonormal polynomials can also be reused, for the basis
$u_0^*,u_1^*,u_2^*$ stay the same when $y_i$'s are different. However,
the method using orthonormal polynomials has no need to solve linear
equations and has better condition number. So it has advantages over
the one using normal equation in this case.
\newpage
\section{programming}
A.Run code/ProblemA.m by matlab to get all the results.\\
B.Run code/ProblemB.m by matlab to get all the results.\\


\end{document}
